
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 1593. -- [Usaco2008 Feb]Hotel -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>1593: [Usaco2008 Feb]Hotel</h2><span class=green>Time Limit: </span>10 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>64 MB<br><span class=green>Submit: </span>125&nbsp;&nbsp;<span class=green>Solved: </span>78<br>[<a href='submitpage.php?id=1593'>Submit</a>][<a href='problemstatus.php?id=1593'>Status</a>][<a href='bbs.php?id=1593'>Discuss</a>]</center><h2>Description</h2><div class=content> 
    奶牛们最近的旅游计划，是到苏必利尔湖畔，享受那里的湖光山色，以及
明媚的阳光。作为整个旅游的策划者和负责人，贝茜选择在湖边的一家著名的
旅馆住宿。这个巨大的旅馆一共有N (1 <= N <= 50,000)间客房，它们在同一层
楼中顺次一字排开，在任何一个房间里，只需要拉开窗帘，就能见到波光粼粼的
湖面。

    贝茜一行，以及其他慕名而来的旅游者，都是一批批地来到旅馆的服务台，
希望能订到D_i (1 <= D_i <= N)间连续的房间。服务台的接待工作也很简单：
如果存在r满足编号为r..r+D_i-1的房间均空着，他就将这一批顾客安排到这些
房间入住；如果没有满足条件的r，他会道歉说没有足够的空房间，请顾客们另
找一家宾馆。如果有多个满足条件的r，服务员会选择其中最小的一个。

    旅馆中的退房服务也是批量进行的。每一个退房请求由2个数字X_i、D_i
描述，表示编号为X_i..X_i+D_i-1 (1 <= X_i <= N-D_i+1)房间中的客人全部
离开。退房前，请求退掉的房间中的一些，甚至是所有，可能本来就无人入住。

    而你的工作，就是写一个程序，帮服务员为旅客安排房间。你的程序一共
需要处理M (1 <= M < 50,000)个按输入次序到来的住店或退房的请求。第一个
请求到来前，旅店中所有房间都是空闲的。

</div><h2>Input</h2><div class=content>* 第1行: 2个用空格隔开的整数：N、M

* 第2..M+1行: 第i+1描述了第i个请求，如果它是一个订房请求，则用2个数字
              1、D_i描述，数字间用空格隔开；如果它是一个退房请求，用3
              个以空格隔开的数字2、X_i、D_i描述

</div><h2>Output</h2><div class=content>* 第1..??行: 对于每个订房请求，输出1个独占1行的数字：如果请求能被满足  
             ，输出满足条件的最小的r；如果请求无法被满足，输出0
</div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>10 6<br />
1 3<br />
1 3<br />
1 3<br />
1 3<br />
2 5 5<br />
1 6<br />
<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata>1<br />
4<br />
7<br />
0<br />
5<br />
</span></div><h2>HINT</h2>
			<div class=content><p></p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search=Gold'>Gold</a></p></div><center>[<a href='submitpage.php?id=1593'>Submit</a>][<a href='problemstatus.php?id=1593'>Status</a>][<a href='bbs.php?id=1593'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
